package solution.dp;

import java.util.Stack;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class MaxAreaUnderHistogram {

	static class Item {
		Integer height;
		Integer pos;

		public Item(int height, int pos) {
			this.height = height;
			this.pos = pos;
		}

		@Override
		public String toString() {
			return "<" + height + "," + pos + ">";
		}
	}

	public long getMaxArea(int[] histogram) {
		long maxArea = 0;
		if (histogram == null || histogram.length == 0)
			return maxArea;

		Stack<Item> stk = new Stack<Item>();
		stk.push(new Item(Integer.MIN_VALUE, -1));
		for (int i = 0; i <= histogram.length; i++) {
			Item cur = new Item((i < histogram.length ? histogram[i]
					: Integer.MIN_VALUE), i);
			if (cur.height > stk.peek().height) {
				stk.push(cur);
				continue;
			}

			while (stk.size() > 1) {
				Item prev = stk.peek();
				long area = (i - prev.pos) * prev.height;
				if (area > maxArea) {
					maxArea = area;
				}
				prev.height = cur.height;
				if (prev.height > stk.get(stk.size() - 2).height) {
					break;
				}
				stk.pop();
			}
		}
		return maxArea;
	}

	@Test
	public void test() {
		int[][] data = new int[][] { //
		//
				{ 1, 2, 3, 1, 5, 1, 5, 2 }, { 8 }, //
				{ 1, 2, 3, 1, 5, 3, 5, 2 }, { 9 }, //
				{ 1, 2, 3, 1, 5, 0, 4, 1 }, { 5 }, //
				{ 1, 2, 3, 1, 5, 0, 5, 3 }, { 6 }, //
				{ 1, 2, 3, 2, 5, 0, 5, 2 }, { 8 }, //
				{ 1, 2, 3, 0, 9, 0, 5, 2 }, { 9 }, //
		};

		for (int i = 0; i < data.length; i += 2) {
			Assert.assertEquals(data[i + 1][0], getMaxArea(data[i]));
		}
	}
}
